package _递归;

import java.util.*;

class _hash {
    // 两数之和（输入二叉树） https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/

    public boolean findTarget(TreeNode root, int k) {
        HashSet<Object> set = new HashSet<>();
        return preorder(root, set, k);
    }

    private boolean preorder(TreeNode root, HashSet<Object> set, int k) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return preorder(root.left, set, k) || preorder(root.right, set, k);
    }


    // 第一题
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) return new int[]{i, map.get((target - nums[i]))};
            map.put(nums[i], i);
        }
        return null;
    }

    private void swap(char[] chars, int l, int r) {
        char temp = chars[r];
        chars[r] = chars[l];
        chars[l] = temp;
    }

    //  2810:故障键盘
    //  输入：s = "string"
    //  输出："rtsng"
    public String finalString(String s) {
        StringBuilder curString = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (aChar == 'i') {
                curString.reverse();
            } else curString.append(aChar);

        }
        return curString.toString();
    }

    // 217 : 是否存在重复元素
    public boolean containsDuplicate(int[] nums) {
        // 用hash来去重
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            } else {
                set.add(num);
            }
        }
        return false;
    }

    // 219 ：存在重复元素II,
    // [1,2,3,1,2,3]
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // key存元素，value存最近一次出现的索引
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) { // 如果元素已经存在
                int distance = i - map.get(nums[i]); // 计算当前索引与之前索引的距离
                if (distance <= k) {
                    return true; // 如果距离 <= k，返回 true
                }
                map.put(nums[i], i); // 更新元素的最新索引
            } else {
                map.put(nums[i], i);
            }
        }
        return false;
    }

    // 242: 有效字母的异位数，用数组来模拟哈希表
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        for (int count : record) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

    // 49：字母异位词分组：https://leetcode.cn/problems/group-anagrams/description/
    // 使用hash，关键在于获得一组异位词的 相同的唯一键, 拿着这个键去存异位词
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            // 获得键
            String key = new String(chars);
            // 获得值
            List<String> value = map.getOrDefault(key, new ArrayList<>());
            value.add(s);
            map.put(key, value);
        }
        return new ArrayList<List<String>>(map.values());
    }

    // 383：赎金信：https://leetcode.cn/problems/ransom-note/
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];
        // 统计 magazine 中每个字符的出现次数
        for (char c : magazine.toCharArray()) {
            count[c - 'a']++;
        }
        // 遍历 ransomNote 中的字符，尝试消耗
        for (char c : ransomNote.toCharArray()) {
            if (--count[c - 'a']< 0) {
                return false;
            }
        }
        return true;
    }
    // 205：同构字符串：https://leetcode.cn/problems/isomorphic-strings/
    public boolean isIsomorphic(String s, String t) {
        // todo
        return true;
    }


    // 697：todo 数组的度：https://leetcode.cn/problems/degree-of-an-array/description/
    // 经典的题
    // 具有相同的出现频次最大的度的最短连续子数组
    public int findShortestSubArray(int[] nums) {
        // key保存数字本身，value[0]保存出现次数, value[1]保存起始下标
        Map<Integer, Integer[]> map = new HashMap<>();
        // max[0]记录出现次数， max[1]记录最短数组长度
        int[] max = {1, 1};
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                // 第一次出现，初始化为{1,i}
                map.put(nums[i], new Integer[]{1, i});
            } else {
                // 多次出现
                Integer[] cur = map.get(nums[i]);
                cur[0] += 1;
                // 如果出现次数更大，或者出现次数相同，长度更短
                if (cur[0] > max[0] || (cur[0] == max[0] && i - cur[1] + 1 < max[1])) {
                    max = new int[]{cur[0], i - cur[1] + 1};
                }
            }
        }
        return max[1];
    }

    // 子数组问题：前缀和
    // ========================================================================
    // 560：和为 k 的子数组个数：https://leetcode.cn/problems/subarray-sum-equals-k/
    public int subarraySum(int[] nums, int k) {
        // key 保存前缀和，value保存其出现次数（可能有不同的起点对应着相同的前缀和）
        Map<Integer, Integer> map = new HashMap<>();
        int pre = 0, count = 0;
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            // 对于当前元素，看是否存在 pre-k 的前缀和
            if (map.containsKey(pre - k))
                count += map.get(pre - k);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    // 523:连续子数组和: https://leetcode.cn/problems/continuous-subarray-sum/
    // 同余定理：如果两个整数m、n满足 n-m 能被 k 整除，那么 n和 m对k 同余
    public boolean checkSubarraySum(int[] nums, int k) {
        // key 保存前缀和的余数，value保存其位置
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            // 余数
            int mod = pre % k;
            // 满足同余定理（两个前缀和对 k 同余了，n-m即为要求的子数组）
            if (map.containsKey(mod) && i - map.get(mod) > 1) {
                return true;
            }
            // 不同余数时才添加，（保留第一次的余数，防止连续相同覆盖 例如：6，6，6 k=6）
            if (!map.containsKey(mod))
                map.put(mod, i);
        }
        return false;
    }

    // 713：todo 乘积小于k的子数组：https://leetcode.cn/problems/subarray-product-less-than-k/description/


    // 238: 100题 除自身以外数组的乘积：https://leetcode.cn/problems/product-of-array-except-self/
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] L = new int[n];
        int[] R = new int[n];
        int[] answer = new int[n];
        // 填充左侧乘积数组
        L[0] = 1; // 第一个元素左侧没有元素
        for (int i = 1; i < n; i++) {
            L[i] = L[i - 1] * nums[i - 1];
        }
        // 填充右侧乘积数组，从右向左遍历
        R[n - 1] = 1; // 最后一个元素右侧没有元素
        for (int i = n - 2; i >= 0; i--) {
            R[i] = R[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }

}















